package top.humbleyuan.dichotomy;

/**
 * @Author HumbleYuan
 * @Date 2020/5/20 21:05
 * @Des 寻找正序数组的中位数
 */
public class LeetCode_4 {
    public static void main(String[] args) {
        // 归并
        //m1();

        // 二分
        m2();
    }

    // 归并思想，时间复杂度(m + n),不满足log(m + n)
    private static void m1() {

        int[] nums1 = {1,3};
        int[] nums2 = {2};
        // 利用归并思想找到中位数
        int allLen = nums1.length + nums2.length;
        int index1, index2 = 0;
        if(allLen % 2 == 1) {
            index1 = allLen / 2 + 1;
        } else {
            index1 = allLen / 2;
            index2 = index1 + 1;
        }

        int count = 0;
        int l1 = 0, l2 = 0;
        float res = 0;
        while(count < index1) {
            if(l2 >= nums2.length || (l1 < nums1.length && nums1[l1] < nums2[l2])) {
                res = nums1[l1++];
            } else {
                res = nums2[l2++];
            }
            count ++;
        }

        if(index2 != 0) {
            res += (nums1[l1] < nums2[l2] ? nums1[l1] : nums2[l2]);
            res = res / 2;
        }

        System.out.println(res);
    }

    private static void m2() {
        int[] nums1 = {1,2,5,6};
        int[] nums2 = {3,4,7,8};

        int allLen = nums1.length + nums2.length;

        // 使用如果偶数则找两个中位数，奇数则计算出的两个数是一样的
        int midLoc1 = (allLen + 1) / 2;
        int midLoc2 = (allLen + 2) / 2;

        double res = 0;
        if(midLoc1 == midLoc2) {
            res = findKth(nums1, 0, nums2, 0, midLoc1);
        } else {
            res = (findKth(nums1, 0, nums2, 0, midLoc2) + findKth(nums1, 0, nums2, 0, midLoc1)) / 2.0;
        }

        System.out.println(res);
    }

    public static int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        // 处理边界条件
        // 如果某一个数组为空，则只需要返回另一个数组里第k个数即可
        if(i >= nums1.length) {
            return nums2[j + k - 1];
        }

        if(j >= nums2.length) {
            return nums1[i + k - 1];
        }

        // 如果k == 1,那么只需要返回较小的一个数
        if(k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }


        // 这里注意判断index是否超过了length
       int midVal1 = i + k / 2 - 1 < nums1.length ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
       int midVal2 = j + k / 2 - 1 < nums2.length ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;

       if(midVal1 < midVal2) {
           return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
       } else {
           return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
       }
    }
}
